package h0808;

import java.util.*;
/**
  * @description 743. 网络延迟时间
  * @author 不知名帅哥
  * @date 2024/8/8 23:46
  * @version 1.0
*/
public class NetworkDelayTime {

    static class Node {
        int vertex;
        int time;

        Node(int vertex, int time) {
            this.vertex = vertex;
            this.time = time;
        }
    }

    public int networkDelayTime(int[][] times, int n, int k) {
        // 使用邻接表表示图
        Map<Integer, List<Node>> graph = new HashMap<>();
        for (int[] time : times) {
            graph.computeIfAbsent(time[0], v -> new ArrayList<>()).add(new Node(time[1], time[2]));
        }

        // 初始化距离数组，所有节点的距离设为无穷大
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;

        // 优先队列，按照节点距离排序
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(node -> node.time));
        pq.add(new Node(k, 0));

        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int currentVertex = current.vertex;
            int currentTime = current.time;

            if (currentTime > dist[currentVertex]) {
                continue;
            }

            if (graph.containsKey(currentVertex)) {
                for (Node neighbor : graph.get(currentVertex)) {
                    int newDist = currentTime + neighbor.time;
                    if (newDist < dist[neighbor.vertex]) {
                        dist[neighbor.vertex] = newDist;
                        pq.add(new Node(neighbor.vertex, newDist));
                    }
                }
            }
        }

        // 找到所有节点中的最长时间
        int maxTime = Arrays.stream(dist).skip(1).max().orElse(-1);
        return maxTime == Integer.MAX_VALUE ? -1 : maxTime;
    }

    public static void main(String[] args) {
        NetworkDelayTime solution = new NetworkDelayTime();
        int[][] times = {{2, 1, 1}, {2, 3, 1}, {3, 4, 1}};
        int n = 4;
        int k = 2;
        int result = solution.networkDelayTime(times, n, k);
        System.out.println(result); // 输出结果为2
    }
}
